#include "btree.h"

void init_btpage(btpage_t *page)
{
  int i;
  page->keycount = 0;

  for (i = 0; i < MAXKEYS; i++) {
    page->key[i] = no_key();
    page->child[i] = NIL;
  }

  page->child[MAXKEYS] = NIL;
}

rrn_t get_btpage(FILE *file)
{
  fseek(file,0,SEEK_END);
  return (ftell(file) - sizeof(rrn_t)) / sizeof(btpage_t);
}

void save_root(FILE *file, rrn_t root)
{
  fseek(file,0,SEEK_SET);
  fwrite(&root,sizeof(rrn_t),1,file);
}

rrn_t get_root(FILE *file)
{
  fseek(file,0,SEEK_END);
  long pos = ftell(file);
  rrn_t root = 0;
  btpage_t page;

  // não existe registro no arquivo
  if (pos == 0) {
    save_root(file,root);
    init_btpage(&page);
    btwrite(file,0,&page);

    return root;
  }

  fseek(file,0,SEEK_SET);
  fread(&root,sizeof(rrn_t),1,file);

  btread(file,root,&page);

  return root;
}

void btread(FILE *file, rrn_t rrn, btpage_t *page_ptr)
{
  // somo para conter tbm o cabeçalho
  fseek(file,(long)rrn * sizeof(btpage_t) + sizeof(rrn_t), SEEK_SET);
  fread(page_ptr,sizeof(btpage_t),1,file);
}

void btwrite(FILE *file, rrn_t rrn, btpage_t *page_ptr)
{
  // somo para conter tbm o cabeçalho
  fseek(file,(long)rrn * sizeof(btpage_t) + sizeof(rrn_t), SEEK_SET);
  fwrite(page_ptr,sizeof(btpage_t),1,file);
}

// 1 em caso de sucesso, 0 caso contrário
int btsearchnode(ChavePrimaria key, btpage_t *page_ptr, rrn_t *pos)
{
  int i;

  for (i = 0; i < page_ptr->keycount && key.inscricao > page_ptr->key[i].inscricao; i++);

  *pos = i;

  return *pos < page_ptr->keycount && key.inscricao == page_ptr->key[*pos].inscricao;
}

void ins_in_page(ChavePrimaria key, rrn_t child, btpage_t *page_ptr)
{
  int i;
  for (i = page_ptr->keycount; key.inscricao < page_ptr->key[i-1].inscricao && i > 0; i--) {
    page_ptr->key[i] = page_ptr->key[i-1];
    page_ptr->child[i+1] = page_ptr->child[i];
  }

  page_ptr->keycount++;
  page_ptr->key[i] = key;
  page_ptr->child[i + 1] = child;
}

void btsplit(FILE *file, ChavePrimaria key, rrn_t r_child, btpage_t *p_oldpage, ChavePrimaria *promo_key, rrn_t *promo_r_child, btpage_t *p_newpage)
{
  int i;
  rrn_t mid;
  ChavePrimaria workkeys[MAXKEYS + 1];
  rrn_t workch[MAXKEYS + 2];

  for (i = 0; i < MAXKEYS; i++) {
    workkeys[i] = p_oldpage->key[i];
    workch[i] = p_oldpage->child[i];
  }

  workch[i] = p_oldpage->child[i];

  for (i = MAXKEYS; key.inscricao < workkeys[i-1].inscricao && i > 0; i--) {
    workkeys[i] = workkeys[i-1];
    workch[i + 1] = workch[i];
  }

  workkeys[i] = key;
  workch[i + 1] = r_child;

  *promo_r_child = get_btpage(file);

  init_btpage(p_newpage);

  for (i = 0; i <= MINKEYS; i++) {
    p_oldpage->key[i] = workkeys[i];
    p_oldpage->child[i] = workch[i];

    p_newpage->key[i] = workkeys[i + 1 + MINKEYS];
    p_newpage->child[i] = workch[i + 1 + MINKEYS];

    p_oldpage->key[i + MINKEYS] = no_key();
    p_oldpage->child[i + 1 + MINKEYS] = NIL;
  }

  p_oldpage->child[MINKEYS] = workch[MINKEYS];
  p_newpage->child[MINKEYS] = workch[i + 1 + MINKEYS];

  p_oldpage->keycount = MINKEYS;
  p_newpage->keycount = MAXKEYS - MINKEYS;

  *promo_key = workkeys[MINKEYS];
}

// uma chave inválida
ChavePrimaria no_key()
{
  ChavePrimaria payload;
  payload.inscricao = 0; // valor aleatório
  payload.byteOffset = 0; // valor aleatório

  return payload;
}

promo_t btinsert(FILE *file, rrn_t rrn, ChavePrimaria key, rrn_t *promo_r_child, ChavePrimaria *promo_key)
{
  printf("%lld - Chave inserindo\n", key.inscricao);
  btpage_t page, newpage;
  int found;
  promo_t promoted;
  rrn_t pos, p_b_rrn;
  ChavePrimaria p_b_key;

  if (rrn == NIL) {
    *promo_key = key;
    *promo_r_child = NIL;
    return YES;
  }

  btread(file,rrn,&page);

  if (found = btsearchnode(key,&page,&pos)) {
    printf("%lld - Chave duplicada\n", key.inscricao);
    return ERROR;
  }

  if ((promoted = btinsert(file,page.child[pos],key,&p_b_rrn,&p_b_key)) != YES) {
    return promoted;
  }

  if (page.keycount < MAXKEYS) {
    ins_in_page(p_b_key,p_b_rrn,&page);
    btwrite(file, rrn, &page);
    return NO;
  }

  btsplit(file, p_b_key, p_b_rrn, &page, promo_key, promo_r_child, &newpage);

  btwrite(file, rrn, &page);
  btwrite(file,*promo_r_child,&newpage);

  return YES;
}

void list_btree(FILE *file)
{
  rrn_t root = get_root(file);
  printf("Pagina raiz: %d\n",root);

  fseek(file,0,SEEK_END);

  long pos = ftell(file);

  long number_of_pages = (pos - sizeof(rrn_t)) / sizeof(btpage_t);

  printf("Total de paginas: %d\n\n",number_of_pages);

  rrn_t i;
  int j;
  btpage_t page;

  for (i = 0; i < number_of_pages; i++) {
    btread(file,i,&page);

    if(i == root){
        printf("---Pagina raiz ----\n");
    }

    printf("RRN: %d\n",i);
    printf("Qtde chave: %d\n",page.keycount);
    printf("Valores: ");

    for (j = 0; j < page.keycount; j++) {
        printf("% lld | ",page.key[j].inscricao);
    }

    printf("\nOffSet : ");
    for (j = 0; j < page.keycount; j++) {
        printf("% lld | ",page.key[j].byteOffset);
    }

    printf("\nFilhos : ");
    for (j = 0; j < page.keycount + 1; j++) {
        printf("% d |",page.child[j]);
    }

    printf("\n\n");
  }

}

rrn_t btcreate_root(FILE *file, ChavePrimaria key, rrn_t left, rrn_t right)
{
  btpage_t page;
  rrn_t rrn;
  rrn = get_btpage(file);
  init_btpage(&page);
  page.key[0] = key;
  page.child[0] = left;
  page.child[1] = right;
  page.keycount = 1;
  btwrite(file,rrn,&page);
  save_root(file,rrn);
  return rrn;
}
